import java.util.LinkedList;
//https://leetcode.cn/problems/valid-parentheses/description/
class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }else {
                    if (stack.isEmpty()) return false;
                    char ch2 = stack.pop();
                    if (ch == ')' && ch2 != '(') return false;
                    if (ch == ']' && ch2 != '[') return false;
                    if (ch == '}' && ch2 != '{') return false;
                }
            }
        }
        if (!stack.isEmpty()) return false;
        return true;
    }
}